package _2022.day._008_565_数组嵌套;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author： YHSimon
 * @date： 2022-07-17 12:59
 */
public class Solution {
    // 下标唯一 85ms
    public int arrayNesting(int[] nums) {
        Set<Integer> set=new HashSet<>();
        Map<Integer,Integer> map=new HashMap<>();
        int ans=0;
        int len=nums.length;
        for(int i=0;i<len;i++){
            int size;
            if(map.containsKey(nums[i])){
                size=map.get(nums[i]);
            }else {
                int index=i;
                while(!set.contains(nums[index])){
                    set.add(nums[index]);
                    index=nums[index];
                }
                size=set.size();
                for(int val:set){
                    map.put(val, size);
                }
            }
            ans=Math.max(ans, size);
            if(ans>nums.length/2){
                return ans;
            }
            set.clear();
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.arrayNesting(new int[]{5,4,0,3,1,6,2}));
    }
}
